#include<stdio.h>
#include "test.h"
#include <stdlib.h>
#include <string.h>



/*void insert_sort_up(int arr[],int n){
    int i = 1;
    int j = 0;
    int k = 1;
    int temp = 0;

    for(;i<n;i++){                        //arr[i]和前面的有序部分作比较，所以i:[1,n-1]
        for(j=0;j<i;j++){                // nums[j]是nums[i]的比较对象，所以j:[0,i)
            if(arr[j]>arr[i]){          //如果满足arr[i] 要插入 在j-1,j 之间的情况。
                temp = arr[j];          //先保存                                    // 插入逻辑复杂
                arr[j] = arr[i];        //再写入
                k = i;                  //获取i的位置

                for(;k>j+1;k--){       //k-1,到 j+1，的位置往后移动一格。
                    arr[k] = arr[k-1];
                }
                arr[j+1] = temp;
            }
        }
    }
}
    */


/*void insert_sort_up(int arr[],int n){
    int i = 1;
    int j = 0;
    int k = 1;
    int temp = 0;
//arr[]={1,6,8,4,7,0,44};
    for(;i<n;i++){                        //arr[i]和前面的有序部分作比较，所以i:[1,n-1]
        temp = arr[i];
        for(j=i-1;j>=0;j--){                // nums[j]是nums[i]的比较对象，所以j:[0,i)
          if(arr[j]>temp){              //  arr[i] 向左做比较，发现应该继续往前找，
            arr[j+1] = arr[j];            //移动。
          }else{
            arr[j+1] = temp;            // 应该插入
            break;
          }
          if(0==j){                 //如果j=0,说明arr[i] 应该插入了。
            arr[j] = temp;
          }

        }
    }
}
    */
void insert_sort_up(int arr[],int n){
    int i = 1;
    int j = 0;

    int temp = 0;

    for(;i<n;i++){                        //arr[i]和前面的有序部分作比较，所以i:[1,n-1]
        temp = arr[i];
        j = i-1;        // nums[j]是nums[i]的比较对象，所以j:[0,i)
        while(j>=0 && arr[j]>temp){      //  arr[i] 向左做比较，如果不满足插入就继续向前找。
            arr[j+1] = arr[j];            //移动
            j--;
        }                                 // 满足或者因为j=0 ,都是一样的逻辑插入
        arr[j+1] = temp;
    }
}





void insert_sort_down(int arr[],int n){
    int i = 1;
    int j = 0;
    int k = 1;
    int temp = 0;

    for(;i<n;i++){              //arr[i]和前面的有序部分作比较，所以i:[1,n-1]    arr[]={1,6,8,4,7,0,44};
        for(j=0;j<i;j++){          // nums[j]是nums[i]的比较对象，所以j:[0,i)
            if(arr[j]<arr[i]){      // 如果
                temp = arr[j];
                arr[j] = arr[i];
                k = i;

                for(;k>j+1;k--){
                    arr[k] = arr[k-1];
                }
                arr[j+1] = temp;
            }
        }
    }
}

void insertion_sort_up(void *base, size_t nmemb, size_t size, 
                   int (*cmp)(const void*, const void*)) {
    char *arr = (char*)base;
    char *key_buf = malloc(size);  // 动态分配临时存储
    
    
    for (size_t i = 1; i < nmemb; i++) {
        memcpy(key_buf, arr + i * size, size);  // 值拷贝而非指针引用
        int j = i - 1;
        
        while (j >= 0 && cmp(arr + j * size, key_buf) > 0) {
            memmove(arr + (j+1)*size, arr + j * size, size);
            j--;
        }
        memcpy(arr + (j+1)*size, key_buf, size);  // 插入原始值
    }
    free(key_buf);  // 释放临时内存
}


// 整型比较函数（示例）
int int_cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}




int main() {
    int arr[]={1,6,8,4,7,0,44};     //不赋值他就是随即的。
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度

    //insert_sort_up(arr, n);  // 调用排序函数
    //insert_sort_down(arr, n);

    insertion_sort_up(arr,n,sizeof(int),int_cmp);

     //打印排序结果
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n ");

    benchmark(insert_sort_up);

    return 0;
}